package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/19 9:42
 */
public class LC650只有两个键的键盘 {

    public static int minSteps(int n) {
//        return dynamicProgramming(n);
//        return recursion(n);
        return memoization(n, new int[n + 1]);
    }

    public static void main(String[] args) {
        System.out.println(minSteps(1000));
    }

    private static int memoization(int n, int[] memo) {
        if (n == 1) return 0;
        if (memo[n] != 0) return memo[n];
        int minFactor = 1;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                minFactor = i;
                break;
            }
        }
        memo[n] = minFactor == 1 ? n : minFactor + memoization(n / minFactor, memo);
        return memo[n];
    }

    private static int recursion(int n) {
        if (n == 1) return 0;
        int minFactor = 1;              //最小因子
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                minFactor = i;
                break;
            }
        }
        if (minFactor == 1) return n;           //最小因子是1代表n是一个质数，只能被1和自身整除
        return minFactor + recursion(n / minFactor);
    }

    private static int dynamicProgramming(int n) {
        int[] dp = new int[n + 1];          //dp[i]代表打印出i个A的最少操作次数
        for (int i = 2; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {      //枚举i的所有因子
                if (i % j != 0) continue;           //j必须是i的因子，只有是i的因子，才能通过一次复制全部并粘贴i/j次得到i个A
                dp[i] = Math.min(dp[i], dp[j] + i / j);
                dp[i] = Math.min(dp[i], dp[i / j] + j);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}
